package question_yuan_quan_zhong_zui_hou_sheng_xia_de_shu_zi_lcof;

/**
 * 动态规划。
 *
 * 状态定义：
 * dp(n, m)：0, 1, ..., (n - 1)这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字，这个圆圈里剩下的最后一个数字编号。
 *
 * 初始化：
 * dp(0, m) = 0，此时圆圈中只有一个数字0，剩下的最后一个数字编号自然也是0。
 *
 * 状态转移：
 * 记第一个待删除的数字编号k = (m - 1) % n，则删除第一个数字后的编号为：
 *
 * 0, 1, ..., k - 1, k + 1, ..., n - 1
 *
 * 将上述编号进行重新排列如下：
 *
 * k + 1, ..., n - 1, ..., 0, 1, ..., k - 1 (*)
 *
 * 对上述编号进行重新标记如下：
 *
 * 0, 1, ..., n - k - 2, ..., n - k - 1, n - k, ..., n - 2 (**)
 *
 * 对于(**)编号下的继续删除得到的结果，其实是dp(n - 1, m)。而将(**)转换为(*)的坐标变换为(x + k + 1) % n。
 *
 * 因此，dp(n, m) = (dp(n - 1, m) + m) % n
 *
 * 时间复杂度是O(n)。空间复杂度是O(1)。
 *
 * 执行用时：7ms，击败99.88%。消耗内存：36.2MB，击败100.00%。
 */
public class Solution {
    public int lastRemaining(int n, int m) {
        int dp = 0;
        for (int i = 1; i < n; i++) {
            dp = (dp + m) % (i + 1);
        }
        return dp;
    }
}